#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int total;
public:
    // 解法一：暴力解法 回溯 时间复杂度O(n*2^n) 空间复杂度O(n)
//    bool canPartition(vector<int>& nums) {
//        int n = nums.size();
//        total = 0;
//        for(int i=0;i<n;i++)
//        {
//            total += nums[i];
//        }
//        if(total & 1 == 1)
//        {
//            return false;
//        }

//        return dfs(nums,0,0);
//    }

//    bool dfs(vector<int>& nums, int i, int sums)
//    {
//        int n = nums.size();
//        if(sums == total - sums)
//        {
//            return true;
//        }
//        if(i == n)
//        {
//            return sums == total - sums;
//        }

//        // 不选
//        bool ret = dfs(nums, i+1, sums);

//        // 选
//        ret = ret || dfs(nums, i+1, sums + nums[i]);

//        return ret;
//    }

};

//int main()
//{
//    Solution solution;
////    [1,5,11,5]
//    vector<int> nums;
////    nums.push_back(1);
////    nums.push_back(5);
////    nums.push_back(11);
////    nums.push_back(5);
////    [2,2,1,1]
////    nums.push_back(2);
////    nums.push_back(2);
////    nums.push_back(1);
////    nums.push_back(1);
////    [14,9,8,4,3,2]
//    nums.push_back(14);
//    nums.push_back(9);
//    nums.push_back(8);
//    nums.push_back(4);
//    nums.push_back(3);
//    nums.push_back(2);
//    bool ret = solution.canPartition(nums);
//    cout << "ret: " << ret << endl;
//}
